#include <iostream>

using namespace std;

// 采用回溯算法实现机器人踩格子

int getDigitSum(int number)
{
    int sum = 0;
    while(number > 0){
        sum += number % 10;
        number /= 10;
    }
    return sum;
}


bool check(int rows, int cols, int row, int col, int key, bool * visited){
    if(row >= 0 && row < rows && col >= 0 && col < cols 
        && getDigitSum(row) + getDigitSum(col) <= key 
        && !visited[row* cols + col])
	    return true;
    return false;
}


int movingCountCore(int rows, int cols, int row, int col,  int key, bool * visited){
    int count = 0;
    if ( check(rows, cols, row, col, key, visited)){
        visited[row*cols+col] = true;

        count = 1 + movingCountCore(rows,cols,row+1,col,key, visited) 
            + movingCountCore(rows,cols,row-1,col,key, visited)
            + movingCountCore(rows,cols,row,col+1,key, visited)
            + movingCountCore(rows,cols,row,col-1,key, visited);
    }
    return count;
}

int movingCount(int rows, int cols, int key){
    if ( rows <= 0 || cols <= 0 || key < 0 ){
        return 0;
    }
    bool * visited = new bool[cols*rows];
    // 初始化
    for ( int i=0; i< cols*rows; i++){
        visited[i] = false;
    }
	int count = movingCountCore(rows, cols,0, 0, key, visited);
    delete[] visited;
    return count;
}

int main(void){
    int count = movingCount(5, 10, 10);
    cout << "expect is 44: " << count << endl;
    count = movingCount(10, 1, 10);
    cout << "expect is 10: " << count << endl;
    return  0;
}